Thành Cát Tư Hãn cuối cùng cho phép Triết Biệt tiến hành viễn chinh cùng với Tốc Bất Đài với vai trò là phó tư lệnh,[6] quân Mông Cổ tiến đến thành phố Derbent, là thành từ chối đầu hàng. Triết Biệt hứa tha cho thành để đối lấy người dẫn đường đưa họ qua Kavkaz. Để cảnh báo những người dẫn đường chớ dùng thủ đoạn, quân Mông Cổ hành quyết một trong số họ. Người Mông Cổ phải trả giá đắt để vượt dãy Kavkaz, họ phải bỏ lại các vũ khí công thành và mất hàng trăm sinh mạng do giá lạnh.[12]

Sau khi vượt dãy Kavkaz, quân Mông Cổ phải đối diện với một liên minh gồm các bộ tộc Bắc Kavkaz là Lezgin, Alan và Cherkes- tập hợp được một quân đội vào khoảng 50.000 binh sĩ.[13] Hội quân với họ là người Cuman, một dân tộc Đột Quyết sở hữu một hãn quốc rộng lớn trải từ hồ Balkhash đến biển Đen. Người Cuman cũng thuyết phục người Bulgar Volga và người Khazar tham gia. Khả hãn của người Cuman là Koten đặt quân đội của mình dưới quyền em trai Yuri và con trai Daniel. Trận chiến đầu tiên giữa liên minh và quân Mông Cổ không dứt khoát, song quân Mông Cổ thuyết phục được người Cuman từ bỏ liên minh bằng cách nhắc lại về tình hữu nghị Đột Quyết-Mông Cổ và hứa hẹn chia phần chiến lợi phẩm thu được từ các bộ tộc Kavkaz.[14]

Với dàn xếp này, quân Mông Cổ tấn công liên quân và đánh tan đối thủ. Sau đó, quân Mông Cổ tiếp tục tấn công người Cuman, lực lượng này đương thời đã bị phân thành hai nhóm, tuy nhiên người Mông Cổ tiêu diệt cả hai quân đội và hành quyết mọi tù nhân trước khi cướp phá Astrakhan.[15] Quân Mông Cổ bắt đầu truy kích người Cuman khi họ chạy theo hướng tây bắc.[16]

Người Venezia cử một phái đoàn đến chỗ quân Mông Cổ, và họ dàn xếp một liên minh mà theo đó thống nhất rằng quân Mông Cổ sẽ tiêu diệt bất kỳ trạm mậu dịch châu Âu nào khác mà họ đi qua.[17] Khi truy kích người Cuman, Triết Biệt phái một phân đội đến Krym, tại đây có các trạm mậu dịch của Cộng hòa Genova. Quân Mông Cổ chiếm lĩnh và cướp bóc thành phố Soldaia của người Genova. Trong khi đó, Koten đào thoát đến triều đình của con rể là Thân vương Mstislav Mstislavich của Galich.[16] Koten cảnh báo Mstislav Mstislavich: "Hôm nay quân Mông Cổ đã chiếm lãnh thổ của chúng tôi và ngày mai họ sẽ đoạt lấy của các con".[18] Tuy nhiên, người Cuman bị phớt lờ trong gần một năm do Rus bị người Cuman tập kích trong nhiều thập niên. Tuy nhiên, khi tin tức truyền đến Kiev rằng người Mông Cổ đang hành quân dọc sông Dniester, Rus hưởng ứng.[19] Mstislav Mstislavich tập hợp một liên minh gồm các thân vương Rus Kiev, trong đó có Mstislav III của Kiev và Thân vương Yuri II của Vladimir-Suzdal- người hứa hẹn hỗ trợ. Các thân vương Rus sau đó bắt đầu tập hợp quân đội và tiến đến điểm hội quân.[15]